package mo.tags.greedy;

import java.util.Arrays;
import java.util.Comparator;

public class L870 {

    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        int n = nums1.length;
        int[] res = new int[n];
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, Comparator.comparingInt(i2 -> nums2[i2]));

        int left = 0, right = n - 1;
        for (int i = 0; i < n; i++) {
            if (nums1[i] > nums2[idx[left]]) {
                res[idx[left]] = nums1[i];
                left++;
            } else {
                res[idx[right]] = nums1[i];
                right--;
            }
        }
        return res;
    }

}
